import java.util.Arrays;

public class LeetCode106 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // 如果输入的数组为空，则返回null
        if (inorder.length == 0 || postorder.length == 0) {
            return null;
        }

        // 后序遍历的最后一个元素是当前树的根节点
        int rootValue = postorder[postorder.length - 1];
        TreeNode root = new TreeNode(rootValue);

        // 在中序遍历中找到根节点的位置
        int rootIndexInInorder = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootValue) {
                rootIndexInInorder = i;
                break;
            }
        }

        // 根据根节点的位置切分中序遍历数组
        // 左子树的中序遍历部分
        int[] inLeft = Arrays.copyOfRange(inorder, 0, rootIndexInInorder);
        // 右子树的中序遍历部分
        int[] inRight = Arrays.copyOfRange(inorder, rootIndexInInorder + 1, inorder.length);

        // 根据根节点的位置切分后序遍历数组
        // 左子树的后序遍历部分
        int[] postLeft = Arrays.copyOfRange(postorder, 0, rootIndexInInorder);
        // 右子树的后序遍历部分
        int[] postRight = Arrays.copyOfRange(postorder, rootIndexInInorder, postorder.length - 1);

        // 递归构建左子树和右子树
        root.left = buildTree(inLeft, postLeft);
        root.right = buildTree(inRight, postRight);

        // 返回构建好地树的根节点
        return root;
    }
}
